package leetcode.test1;

class Solution {
    public int minCut(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        int[] minCut = new int[len + 1];
        for (int i = 0; i <= len; i++) {
            minCut[i] = i - 1;
        }
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (isPal(s, j, i - 1)) {
                    minCut[i] = Math.min(minCut[i], minCut[j] + 1);
                }
            }
        }
        return minCut[len];
    }

    public boolean isPal(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

public class Test10 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret = solution.minCut("aab");
        System.out.println(ret);
    }
}
